/*
 * TODO : ....
 *
 * http://hi.baidu.com/neutblue/blog/item/de224d2dedfb59e58b139945.html
 */


#include "str_array.h"

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

static int
kmp_nv0(const byte * nd, size_t nd_len, int * nv)
{
	int j = 0;
	int k = -1;

	nv[0] = -1; // ???

	while (j < nd_len - 1) {
		if (nd[j] == nd[k] || k == -1) {
			nv[++j] = ++k;
		}
		else {
			printf(" >>> k : %d --> %d \n", k, nv[k]);
			k = nv[k]; // ???
		}
	}

	printf("\n ---------------------------------------- \n");
	for (int z = 0; z < nd_len; ++z) {
		printf(" %d,", nv[z]);
	}
	printf("\n ---------------------------------------- \n");

	return 0;
}

static int
kmp_nv00(const byte * nd, size_t nd_len, int * nv)
{
	int j = 0;
	int k = -1;

	nv[0] = -1;

	while (j < nd_len) {
		if (nd[j] == nd[k] || k == -1) {
			++j;
			++k;
			if (nd[j] != nd[k]) {
				nv[j] = k;
			}
			else {
				nv[j] = nv[k];
			}
		}
		else {
			k = nv[k];
		}
	}

	printf("\n ---------------------------------------- \n");
	for (int z = 0; z < nd_len; ++z) {
		printf(" %d,", nv[z]);
	}
	printf("\n ---------------------------------------- \n");

	return 0;
}

static int
kmp_nv(const byte * nd, size_t nd_len, int * nv)
{
	int i = 0;
	int j = 2;

	nv[0] = -1;
	nv[1] = 0;

	for (; j < nd_len; ++j) {
		if (nd[i] == nd[j - 1]) {
			++i;
		}
		else {
			printf(" >>> i : %d --> %d \n", i, nv[i]);
			i = 0;
		}
		nv[j] = i;
	}

	printf("\n ------------------------------------- \n");
	for (int z = 0; z < nd_len; ++z) {
		printf(" %d,", nv[z]);
	}
	printf("\n ------------------------------------- \n");

	return 0;
}

void
test_kmp_nv()
{
	const char * str = "abcabcxxabcabcabcd";

	printf("%s \n", str);

	int * nv = malloc(sizeof(int) * strlen(str));

	kmp_nv((const byte *)str, strlen(str), nv);
	kmp_nv0((const byte *)str, strlen(str), nv);
	kmp_nv00((const byte *)str, strlen(str), nv);
}

static int
kmp(const byte * hs, size_t hs_len, const byte * nd, size_t nd_len)
{
	int posi = -1;

	int * nv = malloc(sizeof(int) * nd_len);
	kmp_nv(nd, nd_len, nv);

	int i = 0;
	int j = 0;

	for (;;) {
		for (; j < nd_len && i < hs_len - nd_len && hs[i] == nd[j]; ++i, ++j) {}

		if (j != nd_len) {
			if (i < hs_len - nd_len) {
				if (j) {
					j = nv[j];
				}
				else {
					++i;
				}
			}
			else {
				break;
			}
		}
		else {
			posi = i - nd_len;
			break;
		}
	}

	free(nv);
	return posi;
}

int
sq_str_kmp(const sq_str * haystack, const sq_str * needle)
{
	return kmp(haystack->data, haystack->len, needle->data, needle->len);
}

#if 0

{
	int j = 0;
	int k = -1;

	nv[0] = -1; // ???

	while ( j < nd.len - 1) {
		if (t.data[j] == t.data[k] || k == -1) {
			nv[++j] = ++k;
		}
		else {
			k = nv[k]; // ???
		}
	}
}

#endif

